The use of binary trees and the like is well known in the art. The subject is discussed extensively in treatises such as "The Art of Computing--Sorting and Searching" by Knuth, Addison-Wesley, 1975; "Algorithms in C" by Robert Sedgewick; Addison-Wesley, 1990; and "Data Structures and Algorithms" by Al Aho et al, Addison-Wesley, 1983. Generally, it can be said that the building of trees, the searching of such trees and the insertion of nodes into such trees is relatively easy and well understood. The deletion of nodes is generally more difficult. It is well known that one way of deleting a tree node is to replace it with another existing node in the tree. First, the replacing node has to be determined and then the pointers in affected nodes of the tree are adjusted to reflect the replacement, all while preserving the properties of tree construction in the particular tree in question. The major problem in deletion is often that of determining the replacing node. Also, depending on the particular type of tree in question, there can be many individual cases, depending on the location in the tree of the node to be deleted, which must be accounted for in preserving the properties. Thus, deletion is relatively simple in certain types of trees such as simple binary trees, but very difficult in other types of trees. An example of the latter is the Patricia (Practical Algorithm to Retrieve Information Coded in Alphanumeric) tree.
A Patricia tree is an efficient way of storing keys of arbitrary length. It can be searched by traversing the tree with only one full key comparison, which is done at the end of the search to determine if an actual match has been found on the search key. Every node in a Patricia tree is reached by a unique path through the tree. Further, Patricia trees eliminate the problem of one way branching which occurs in other types of search trees, which means that in a system of N keys, there are only N nodes in the search tree. In other types of trees there can be many more nodes, representing wasted space, than there are keys. Because of these desirable characteristics, the Patricia tree is popular in certain types of applications such as indexing documents on actual text. However, at the present time, Patricia trees have one great disadvantage. Until now, to my knowledge, no one has discovered any reasonable method of deleting nodes in a Patricia tree. Sedgewick and Knuth, for example, describe in detail the algorithms for building, searching and inserting nodes into a Patricia tree. However, the problem of deleting nodes is not even mentioned. Aho does not discuss Patricia trees. Neither does D. R. Morrison discuss deleting nodes in his original paper "Patricia--Practical Algorithm to Retrieve Information Coded in Alphanumeric", Journal of the ACM, Vol. 15, 1968. In all instances known to me of the use of a Patricia tree, nodes are deleted by rebuilding the entire tree. The disadvantages of this are obvious, especially in trees which can be quite large or in which deletion occurs frequently. As a result, the Patricia tree has not gained widespread use, except in applications in which node deletion is relatively infrequent or in which the tree is relatively small. Thus, there is a great need to determine a way of dynamically deleting nodes of a Patricia tree in reasonable time and thereby expand the use of this desirable tree to many more areas of use.